package com.chunlin.compare;

import java.util.Arrays;
import java.util.PriorityQueue;

public class CompareTest extends Object {
    public static void main(String[] args) {
//        test1();
//        test2();
//        test3();
//        test4();
//        test5();
//        test6();
//        test7();
        test8();
    }

    //使用PriorityQueue创建大小堆，解决TOPK问题
    private static void test8() {
        int[] array = {4,1,9,2,8,0,7,3,6,5};
        int[] ret1 = smallestK(array, 3);
        int[] ret2 = largestK(array, 3);
        System.out.println(Arrays.toString(ret1));
        System.out.println(Arrays.toString(ret2));
    }

    private static int[] largestK(int[] array, int k) {
        //求最大的K个数,建立小根堆
        if (k <= 0) {
            throw new IllegalArgumentException("i <= 0");
        }

        LessIntCompare lessIntCompare = new LessIntCompare();
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, lessIntCompare);

        //先将前K个元素，创建大根堆
        for (int i = 0; i < k; ++i) {
            priorityQueue.offer(array[i]);
        }
        //从第K+1个元素开始，每次和堆顶元素比较
        for (int i = k; i < array.length; ++i) {
            if (array[i] > priorityQueue.peek()) {
                priorityQueue.poll();
                priorityQueue.offer(array[i]);
            }
        }

        //取出前K个
        int[] ret = new int[k];
        for (int i = 0; i < k; ++i) {
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }

    private static int[] smallestK(int[] array, int k) {
        //求最小的K个数,建立大根堆
        if (k <= 0) {
            throw new IllegalArgumentException("i <= 0");
        }

        GreaterIntCompare greaterIntCompare = new GreaterIntCompare();
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, greaterIntCompare);

        //先将前K个元素，创建小根堆
        for (int i = 0; i < k; ++i) {
            priorityQueue.offer(array[i]);
        }
        //从第K+1个元素开始，每次和堆顶元素比较
        for (int i = k; i < array.length; ++i) {
            if (array[i] < priorityQueue.peek()) {
                priorityQueue.poll();
                priorityQueue.offer(array[i]);
            }
        }

        //取出前K个
        int[] ret = new int[k];
        for (int i = 0; i < k; ++i) {
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }

    private static void test7() {
        //集合框架中的PriorityQueue底层使用堆结构，因此其内部的元素必须要能够比大小
        // PriorityQueue采用了：Comparble和Comparator两种方式
        //1. Comparble是默认的内部比较方式，如果用户插入自定义类型对象时
        // 该类对象必须要实现Comparble接口，并覆写compareTo方法
        //2. 用户也可以选择使用比较器对象，如果用户插入自定义类型对象时
        // 必须要提供一个比较器类，让该类实现Comparator接口并覆写compare方法

//        // JDK中PriorityQueue的实现：
//        public class PriorityQueue<E> extends AbstractQueue<E>
//                implements java.io.Serializable {// ...
//            // 默认容量
//            private static final int DEFAULT_INITIAL_CAPACITY = 11;
//            // 内部定义的比较器对象，用来接收用户实例化PriorityQueue对象时提供的比较器对象
//            private final Comparator<? super E> comparator;
//
//            // 用户如果没有提供比较器对象，使用默认的内部比较，将comparator置为null
//            public PriorityQueue() {
//                this(DEFAULT_INITIAL_CAPACITY, null);
//            }
//
//            // 如果用户提供了比较器，采用用户提供的比较器进行比较
//            public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
//            // Note: This restriction of at least one is not actually needed,
//            // but continues for 1.5 compatibility
//                if (initialCapacity < 1)
//                    throw new IllegalArgumentException();
//                this.queue = new Object[initialCapacity];
//                this.comparator = comparator;
//            }
//
//            // ...
//            // 向上调整：
//            // 如果用户没有提供比较器对象，采用Comparable进行比较
//            // 否则使用用户提供的比较器对象进行比较
//            private void siftUp(int k, E x) {
//                if (comparator != null)
//                    siftUpUsingComparator(k, x);
//                else
//                    siftUpComparable(k, x);
//            }
//
//            // 使用Comparable
//            @SuppressWarnings("unchecked")
//            private void siftUpComparable(int k, E x) {
//                Comparable<? super E> key = (Comparable<? super E>) x;
//                while (k > 0) {
//                    int parent = (k - 1) >>> 1;
//                    Object e = queue[parent];
//                    if (key.compareTo((E) e) >= 0)
//                        break;
//                    queue[k] = e;
//                    k = parent;
//                }
//                queue[k] = key;
//            }
//
//            // 使用用户提供的比较器对象进行比较
//            @SuppressWarnings("unchecked")
//            private void siftUpUsingComparator(int k, E x) {
//                while (k > 0) {
//                    int parent = (k - 1) >>> 1;
//                    Object e = queue[parent];
//                    if (comparator.compare(x, (E) e) >= 0)
//                        break;
//                    queue[k] = e;
//                    k = parent;
//                }
//                queue[k] = x;
//            }
//        }
    }

    //三种方式对比
    //Object.equals
    //因为所有类都是继承自 Object 的，所以直接覆写即可，不过只能比较相等与否
    //Comparable.compareTo需要手动实现接口，侵入性比较强，但一旦实现，每次用该类都有顺序，属于内部顺序
    //Comparator.compare需要实现一个比较器对象，对待比较类的侵入性弱，但对算法代码实现侵入性强
    private static void test6() {
        Card p = new Card(1, "♠");
        Card q = new Card(2, "♠");
        Card o = new Card(1, "♠");

        CardComparator comparator = new CardComparator();
        System.out.println(comparator.compare(p, q));
        System.out.println(comparator.compare(p, o));
        System.out.println(comparator.compare(q, p));
    }

    private static void test5() {
        //对用用户自定义类型，如果要想按照大小与方式进行比较时：在定义类时，实现Comparble接口即可，然后在类中重写compareTo方法
        Card p = new Card(1, "♠");
        Card q = new Card(2, "♠");
        Card o = new Card(1, "♠");

        System.out.println(p.compareTo(q)); // -1,表示p比q小
        System.out.println(p.compareTo(o)); // == 0，表示牌相等
        System.out.println(q.compareTo(p)); // 1,表示q比p大

    }

    private static void test4() {
        //有些情况下，需要比较的是对象中的内容,而不是对象的引用时候,应该如何操作
        //覆写基类的equals
        Card c1 = new Card(1, "♠");
        Card c2 = new Card(1, "♠");
        Card c3 = c1;

        System.out.println(c1.equals(c2));
        System.out.println(c1.equals(c3));
    }

    private static void test3() {
        Card c1 = new Card(1, "♠");
        Card c2 = new Card(1, "♠");
        Card c3 = c1;

        //System.out.println(c1 > c2); // 编译报错
        System.out.println(c1 == c2); // 编译成功 ----> 打印false，因为c1和c2指向的是不同对象
        //System.out.println(c1 < c2); // 编译报错
        System.out.println(c1 == c3); // 编译成功 ----> 打印true，因为c1和c3指向的是同一个对象

        //c1、c2和c3分别是Card类型的引用变量，上述代码在比较编译时：
        //c1 > c2 编译失败
        //c1== c2 编译成功  //这里的==是直接进行引用的比较,也就是地址的比较,而不是调用了equal方法
        //c1 < c2 编译失败
        //从编译结果可以看出，Java中引用类型的变量不能直接按照 > 或者 < 方式进行比较。 那为什么==可以比较？
        //因为==操作符用于比较两个引用是否指向同一个对象。换句话说，它比较的是两个引用变量中存储的内存地址是否相同。这件事是有意义的
        //为什么不能使用>和<操作符,这件事是没有意义的
        //内存地址不是有序的：
        //引用变量存储的是对象在内存中的地址，而内存地址本身不是有序的。地址的值不具有自然的大小关系，因此不能进行大于或小于的比较
        //内存地址的分配由JVM管理，它们的分配是动态的，地址的值没有任何业务意义上的顺序
        //没有定义大小关系：
        //引用类型没有实现类似数值类型那样的自然顺序，因此不能使用>、<、>=、<=等操作符
    }

    //在Java中，基本类型的对象可以直接比较大小
    private static void test2() {
        int a = 10;
        int b = 20;
        System.out.println(a > b);
        System.out.println(a < b);
        System.out.println(a == b);
        char c1 = 'A';
        char c2 = 'B';
        System.out.println(c1 > c2);
        System.out.println(c1 < c2);
        System.out.println(c1 == c2);
        boolean b1 = true;
        boolean b2 = false;
        System.out.println(b1 == b2);
        System.out.println(b1 != b2);
    }

    private static void test1() {
        PriorityQueue<Card> priorityQueue = new PriorityQueue<>();
        //优先级队列底层使用堆，而向堆中插入元素时，为了满足堆的性质，必须要进行元素的比较，而此时Card是没有办法直接进行比较的，因此抛出异常
        priorityQueue.offer(new Card(1, "♠"));
        priorityQueue.offer(new Card(2, "♠"));
    }


}
